package com.example.leetcode.矩阵;

import java.util.ArrayList;
import java.util.List;


/**
 * 螺旋矩阵
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * <p>
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * <p>
 * [行][列]
 */
public class SpiralOrder {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        int rowTop = 0;
        int rowBottom = matrix.length - 1;
        int colLeft = 0;
        int colRight = matrix[0].length - 1;

        while (colLeft <= colRight && rowTop <= rowBottom) {
            // 矩阵顶部
            for (int i = colLeft; i <= colRight; i++) {
                result.add(matrix[rowTop][i]);
            }
            // 矩阵最右列
            for (int i = rowTop + 1; i <= rowBottom; i++) {
                result.add(matrix[i][colRight]);
            }
            if (colLeft < colRight && rowTop < rowBottom) {
                // 矩阵底部
                for (int i = colRight - 1; i >= colLeft; i--) {
                    result.add(matrix[rowBottom][i]);
                }

                // 矩阵最左列
                for (int i = rowBottom - 1; i > rowTop; i--) {
                    result.add(matrix[i][colLeft]);
                }
            }

            // 外层走完，走下一个内层
            rowTop++;
            rowBottom--;
            colLeft++;
            colRight--;
        }

        return result;
    }
}
